package LearnDataStructure.d_图结构.e_最小生成树;

import java.util.ArrayList;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-15 20:02
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.e_最小生成树
 */
/*
适用于无向图
 */
public class f_Prim {

    public static void main(String[] args) {
        f_Prim test = new f_Prim();
        test.usePrim();
    }

    public void usePrim() {
        final int N = 65535;
        int[][] matrix = new int[][] {
                {N,1,3,4,7},
                {1,N,2,N,N},
                {3,2,N,5,8},
                {4,N,5,N,6},
                {7,N,8,6,N}
        };
        int vertexSize = 5;
        Graph graph = new Graph(matrix,vertexSize);
        graph.prim();
    }

    public class Graph {
        //存放顶点的数组
        public int vertexSize = 0;
        //保存从各个顶点出发到其它顶点的距离
        public int[][] dis;
        final int N = 65535;

        /**
         * @param matrix         邻接矩阵
         * @param vertexSize   顶点个数
         */
        public Graph(int[][] matrix ,int vertexSize) {
            this.vertexSize = vertexSize;
            this.dis = matrix;
        }

        /**
         * 没有健壮性判断
         * 比如顶点个数=0的时候
         * 比如顶点个数=1的时候
         */
        public void prim() {
            //最终最小生成树结果的点的集合
            ArrayList<Integer> listU = new ArrayList<Integer>();
            //还没有被判断的点的集合
            ArrayList<Integer> listV = new ArrayList<Integer>();
            //按listU加入点的顺序，有顺序放入边的权值，的集合
            ArrayList<edge> edgeList = new ArrayList<edge>();
            //初始化集合
            listU.add(0);
            for (int i = 1; i < vertexSize; i++) {
                listV.add(i);
            }
            int minPath = 0;
            int pointU = 0;
            int pointV = 0;
            int pointIndexV = 0;
            while (!listV.isEmpty()) {
                minPath = Integer.MAX_VALUE;
                for (int uIndex = 0; uIndex < listU.size(); uIndex++) {
                    for (int vIndex = 0; vIndex < listV.size(); vIndex++) {
                        if (dis[listU.get(uIndex)][listV.get(vIndex)] != N && dis[listU.get(uIndex)][listV.get(vIndex)] < minPath) {
                            minPath = dis[listU.get(uIndex)][listV.get(vIndex)];
                            pointU = listU.get(uIndex);
                            pointV = listV.get(vIndex);
                            pointIndexV = vIndex;
                        }
                    }
                }
                /*
                跳出循环后，代表listU中的所有的点，对listV中的点存在的所有的边
                这些个边全部遍历完毕了，而且找到了最小的边的“权值minPath”和“起始点currentU&currentV”
                 */
                listU.add(pointV);
                listV.remove(pointIndexV);
                edgeList.add(new edge(pointU,pointV,minPath));
            }
            showMST(edgeList);
        }

        public void showMST(ArrayList<edge> edgeList) {
            for (edge edge : edgeList) {
                System.out.println(edge);
            }
        }
    }

    public class edge {
        int start = 0;
        int end = 0;
        int distance = 0;

        public edge(int start, int end, int distance) {
            this.start = start;
            this.end = end;
            this.distance = distance;
        }

        @Override
        public String toString() {
            return "edge{" +
                    "start=" + (char)(start + 'A') +
                    ", end=" + (char)(end + 'A') +
                    ", distance=" + distance +
                    '}';
        }
    }
}
